#include <iostream>
#include <list>
#include <unordered_map>
#include <vector>
#include <string.h>

using std::cout;
using std::endl;
using std::list;
using std::pair;
using std::unordered_map;
using std::iterator;
using std::string;
using std::vector;

#if 0
// 算了，list是个迭代器，再重载怪麻烦的
// 类外定义泛型 display
template<typename Container>
void display(const Container& container) {
    for (const auto& elem : container) {
        std::cout << elem << " ";
    }
    std::cout << "\n";
}

// 类外特化 display 用于 unordered_map
template<typename Key, typename Value>
void display(const unordered_map<Key, Value>& container) {
    for (const auto& [key, value] : container) {
        std::cout << key << ":" << value << " ";
    }
    std::cout << "\n";
}
#endif

class LRUCache{
public:
    LRUCache(size_t capacity = 2);
    ~LRUCache();

    int get(int key);
    void put(int key, int value);

    //    // 不要定义在类里，真是各种麻烦还识别不了
    //    template<typename Container>
    //        void display(const Container& container);
    //
    //    template<typename Key, typename Value>
    //        void display(const unordered_map<Key, Value>& container);

    void displayState() const;

private:
    size_t _capacity;
    //    pair<int, int> _pair;
    list<pair<int, int>> _list;
    //    unordered_map<int, int> _map;     // int, int是不行的，需要迭代器完成映射
    unordered_map<int, list<pair<int, int>>::iterator> _map;     // 需要迭代器完成映射

};

LRUCache::LRUCache(size_t capacity)
    :_capacity(capacity){
    }

LRUCache::~LRUCache(){
    //    // list不会手动析构
    //    if(_list.empty() != true){
    //        delete []_list;
    //    }
}

int LRUCache::get(int key){
    if(_map.count(key) == false){
        return -1;
    }
    else{
        auto it = _map[key];     // 通过_map[key]获取链表迭代器
                                 //      int value = it->second;  // 从链表节点中取出value

                                 //cout << "go into 82 \n";
                                 //cout << it->first << " ";
                                 //cout << it->second << "\n";

        _list.splice(_list.begin(), _list, it);

        return it->second;
    }
}

void LRUCache::put(int key, int value){
    //  cout << "go into 89, line _map.count(key) = " << _map.count(key) << "\n";
    if(_map.count(key) == 1){
        auto it = _map[key];
        //  cout << "go into 91 \n";
        //  cout << it->first << " ";
        //  cout << it->second;
        it->second = value;
        _list.splice(_list.begin(), _list, it);

        return;
    }
    else{

        if(_map.size() >= _capacity){
            int key = _list.back().first;

            _list.pop_back();
            _map.erase(key);
        }

        pair<int, int> _list_pair = {key, value};
        _list.push_front(_list_pair);

        //pair<int, list<pair<int, int>>::iterator> _map_pair = {key, _list.end()};   // end指向的是后一位
        pair<int, list<pair<int, int>>::iterator> _map_pair = {key, _list.begin()};   // end指向的是后一位
        _map.insert(_map_pair);
    } 
}

#if 0
// 类里访问模板会有很多问题，尽量在类外实现
template<typename Container>
void LRUCache::display(const Container& container){
    for(auto & elem : container){
        cout << elem << " ";
    }

    cout << endl;
}


template<typename Key, typename Value>
void display(const unordered_map<Key, Value>& container){
    for(auto & elem : container){
        cout << elem.first << ":" << elem.second << " ";
    }

    cout << endl;
}
#endif

#if 0
// list有一个迭代器，解引用这个可能还得重载，所以这里模板还用不上，囧
void LRUCache::displayState() const {
    std::cout << "--- LRUCache State ---\n";

    // 调用泛型 display 显示 _list
    std::cout << "List: ";
    display(_list);  // 调用 template<typename Container> display

    // 调用特化 display 显示 _map
    std::cout << "Map: ";
    display(_map);   // 调用 template<typename Key, typename Value> display
}
#endif

void LRUCache::displayState() const {
    std::cout << "List (LRU order): ";
    for (const auto& [key, value] : _list) {
        std::cout << key << "=" << value << " ";
    }
    std::cout << "\n";

    std::cout << "Map (key -> node): ";
    for (const auto& [key, it] : _map) {
        std::cout << key << "->[" << it->first << "=" << it->second << "] ";
    }
    std::cout << "\n";
}

void test(){
    vector<pair<string, vector<int>>> input = {
        {"LRUCache", {2}},      // LRUCache(2)
        {"put", {1, 1}},        // put(1, 1)
        {"put", {2, 2}},        // put(2, 2)
        {"get", {1}},           // get(1)
        {"put", {3, 3}},        // put(3, 3)
        {"get", {2}},           // get(2)
        {"put", {4, 4}},        // put(4, 4)
        {"get", {1}},           // get(1)
        {"get", {3}},           // get(3)
        {"get", {4}}            // get(4)
    };

    //    switch(string){   // switch不可以用string比较
    //        case "LRUCache": 
    //    }

    LRUCache* lc = nullptr;     // 不知道初始值大小时，最好用lc声明

    for(auto& command : input){
        [=](){
            cout << command.first << " : ";
            for(auto& num : command.second){
                cout << num << " ";
            }
            cout << "\n";
        }();

        if(command.first ==  "LRUCache"){
            //  static LRUCache lc(command.second[0]); 
            lc = new LRUCache(command.second[0]);
        } 
        else if(command.first == "put" && lc != nullptr){
            lc->put(command.second[0], command.second[1]);
        }
        else if(command.first == "get" && lc != nullptr){
            int val = lc->get(command.second[0]);
            cout << "getval = " << val << "\n";
        }
        lc->displayState();       
    }

}


int main()
{
    test();
    return 0;
}

